package com.iris.dataStructures;

import java.util.Arrays;

/**
 *
 */
public class QuickSort3 {
    public static void main(String args[]) {
        QuickSort3 quicksort = new QuickSort3();
        int[] arrays = new int[]
                {10, 12, 5, 13, 3, 14, 4, 15, 2, 16, 17, 17, 177, 18, 8, 8, 19};
//                {10, 12, 5};
        System.out.println(Arrays.toString(arrays));
        quicksort.subQuickSort(arrays,0,arrays.length-1);

        System.out.println(Arrays.toString(arrays));
    }
    private void subQuickSort(int[] arrays, int start, int end)
    {
        if (start >= end)
        {
            return;
        }
        int middleIndex = subQuickSortCore(arrays, start, end);
        subQuickSort(arrays, start, middleIndex - 1);
        subQuickSort(arrays, middleIndex + 1, end);
    }

    public  int subQuickSortCore(int[] arrays, int start, int end){
        int middleValue = arrays[start];
        int oldStart = start;
        while (start < end)
        {
//            while (arrays[end] >= middleValue && start < end)
//            {
//                end--;
//            }
//            while (arrays[start] <= middleValue && start < end)
//            {
//                start++;
//            }
            while (arrays[start] <= middleValue && start < end)
            {
                start++;
            }
            while (arrays[end] >= middleValue && start < end)
            {
                end--;
            }
            if((start+1)==end){

                System.out.print("");
            }
            System.out.println("start="+start+"==end=="+end);
            swap(arrays,start,end);
        }
//        System.out.println(Arrays.toString(arrays)+"=======swap=end="+end+"==="+arrays[oldStart]+"=="+arrays[end]);
        swap(arrays,oldStart,end);
//        System.out.println(Arrays.toString(arrays));
        return end;
    }


    public  void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
